package com.yanceysong.codetop.s81_s90;

import com.yanceysong.common.TreeNode;

public class S89_Easy_112_路径总和 {
    /**
     * .S89_Easy_112_路径总和
     * .<p>
     * .<a href="https://leetcode.cn/problems/path-sum/">...</a>
     * .<p>
     * .给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
     * .判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
     * .如果存在，返回 true ；否则，返回 false 。
     * .<p>
     * .叶子节点 是指没有子节点的节点。
     * .<p>
     * .核心标签：二叉树、深度优先搜索(DFS)、递归
     * .<p>
     * .示例 1：
     * .<p>
     * .输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
     * .输出：true
     * .解释：等于目标和的根节点到叶节点路径如图所示。路径为：5 → 4 → 11 → 2，总和为 22
     * .<p>
     * .示例 2：
     * .<p>
     * .输入：root = [1,2,3], targetSum = 5
     * .输出：false
     * .解释：树中存在两条根节点到叶子节点的路径：
     * .(1 → 2): 和为 3
     * .(1 → 3): 和为 4
     * .不存在 sum = 5 的根节点到叶子节点的路径。
     * .<p>
     * .示例 3：
     * .<p>
     * .输入：root = [], targetSum = 0
     * .输出：false
     * .解释：由于树是空的，所以不存在根节点到叶子节点的路径。
     * .<p>
     * .提示：
     * .<p>
     * .树中节点的数目在范围 [0, 5000] 内
     * .-1000 <= Node.val <= 1000
     * .-1000 <= targetSum <= 1000
     * .<p>
     * .解题思路：深度优先搜索（DFS）+ 递归
     * .<p>
     * .核心思想：
     * .1. 从根节点开始，递归地遍历每条从根到叶子的路径
     * .2. 每次递归时，将目标和减去当前节点的值，得到剩余需要的和
     * .3. 当到达叶子节点时，检查剩余的和是否等于叶子节点的值
     * .4. 如果任意一条路径满足条件，返回 true；否则返回 false
     * .<p>
     * .关键洞察：
     * .- 必须是根节点到叶子节点的完整路径，中间节点不算
     * .- 叶子节点的定义：左右子节点都为 null
     * .- 使用递归的方式，将问题分解为子问题：
     * ."树是否有路径和为 targetSum" = "左子树是否有路径和为 targetSum - root.val"
     * .或 "右子树是否有路径和为 targetSum - root.val"
     * .<p>
     * .图解示例 1：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
     * .<p>
     * .树的结构：
     * .5
     * ./   \
     * .4      8
     * ./      /  \
     * .11     13   4
     * ./  \          \
     * .7    2          1
     * .<p>
     * .递归过程（寻找路径和为 22）：
     * .<p>
     * .步骤1：从根节点5开始，剩余目标和 = 22 - 5 = 17
     * .5 (当前节点，剩余目标和=17)
     * ./   \
     * .4      8
     * .<p>
     * .步骤2：递归左子树，节点4，剩余目标和 = 17 - 4 = 13
     * .4 (当前节点，剩余目标和=13)
     * ./
     * .11
     * .<p>
     * .步骤3：递归左子树，节点11，剩余目标和 = 13 - 11 = 2
     * .11 (当前节点，剩余目标和=2)
     * ./  \
     * .7    2
     * .<p>
     * .步骤4：递归左子树，节点7（叶子节点），剩余目标和 = 2 - 7 = -5
     * .7 ≠ 2，返回 false
     * .<p>
     * .步骤5：递归右子树，节点2（叶子节点），剩余目标和 = 2
     * .2 == 2，找到路径！返回 true
     * .<p>
     * .找到的路径：5 → 4 → 11 → 2，总和 = 22 ✓
     * .<p>
     * .图解示例 2：root = [1,2,3], targetSum = 5
     * .<p>
     * .树的结构：
     * .1
     * ./   \
     * .2     3
     * .<p>
     * .所有路径：
     * .路径1：1 → 2，和 = 3 ✗
     * .路径2：1 → 3，和 = 4 ✗
     * .没有路径和为 5，返回 false
     * .<p>
     * .边界情况处理：
     * .1. 空树（root == null）：返回 false
     * .2. 只有根节点：检查根节点值是否等于 targetSum
     * .3. 负数节点值：算法依然有效，因为我们只是做减法运算
     * .<p>
     * .时间复杂度：O(n)，其中 n 是树中节点的数量
     * .- 最坏情况下需要遍历所有节点（当目标路径不存在或在最后才找到）
     * .- 每个节点只访问一次
     * .<p>
     * .空间复杂度：O(h)，其中 h 是树的高度
     * .- 递归调用栈的深度等于树的高度
     * .- 最坏情况（链式树）：O(n)
     * .- 最好情况（平衡树）：O(log n)
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 边界条件：空节点返回 false
        if (root == null) {
            return false;
        }

        // 到达叶子节点：检查当前节点值是否等于剩余的目标和
        // 叶子节点的定义：左右子节点都为 null
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        // 递归检查左右子树
        // 将目标和减去当前节点的值，作为子树的新目标和
        // 只要左子树或右子树中有一条路径满足条件，就返回 true
        boolean hasLeftPath = hasPathSum(root.left, targetSum - root.val);
        boolean hasRightPath = hasPathSum(root.right, targetSum - root.val);

        return hasLeftPath || hasRightPath;
    }

    public static void main(String[] args) {
        S89_Easy_112_路径总和 solution = new S89_Easy_112_路径总和();

        System.out.println("=== 路径总和测试开始 ===");

        // 测试1: 示例1 - 存在路径和为22
        System.out.println("\n--- 测试1: 示例1 [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum=22 ---");
        testCase1(solution);

        // 测试2: 示例2 - 不存在路径和为5
        System.out.println("\n--- 测试2: 示例2 [1,2,3], targetSum=5 ---");
        testCase2(solution);

        // 测试3: 示例3 - 空树
        System.out.println("\n--- 测试3: 空树, targetSum=0 ---");
        testCase3(solution);

        // 测试4: 单节点树，目标和匹配
        System.out.println("\n--- 测试4: 单节点树 [1], targetSum=1 ---");
        testCase4(solution);

        // 测试5: 单节点树，目标和不匹配
        System.out.println("\n--- 测试5: 单节点树 [1], targetSum=2 ---");
        testCase5(solution);

        // 测试6: 负数节点值
        System.out.println("\n--- 测试6: 负数节点 [-3,9,-10], targetSum=-4 ---");
        testCase6(solution);

        // 测试7: 目标和为0
        System.out.println("\n--- 测试7: [1,-2,3], targetSum=2 ---");
        testCase7(solution);

        // 测试8: 链式树（左偏）
        System.out.println("\n--- 测试8: 链式树 [1,2,null,3,null,4,null,5], targetSum=15 ---");
        testCase8(solution);

        // 测试9: 多条路径，只有一条满足
        System.out.println("\n--- 测试9: [10,5,15,3,7,null,18], targetSum=18 ---");
        testCase9(solution);

        // 测试10: 所有路径都不满足
        System.out.println("\n--- 测试10: [1,2,3,4,5], targetSum=100 ---");
        testCase10(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: 示例1
     * .树结构：
     * .       5
     * .      / \
     * .     4   8
     * .    /   / \
     * .   11  13  4
     * .  / \       \
     * . 7   2       1
     * .路径：5 → 4 → 11 → 2 = 22
     */
    private static void testCase1(S89_Easy_112_路径总和 solution) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        int targetSum = 22;
        System.out.println("树结构: [5,4,8,11,null,13,4,7,2,null,null,null,1]");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: true)");
        System.out.println("路径: 5 → 4 → 11 → 2 = 22");
        assert result : "应该找到路径和为22";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 示例2
     * .树结构：
     * .   1
     * .  / \
     * . 2   3
     * .路径1: 1 → 2 = 3
     * .路径2: 1 → 3 = 4
     */
    private static void testCase2(S89_Easy_112_路径总和 solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        int targetSum = 5;
        System.out.println("树结构: [1,2,3]");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: false)");
        System.out.println("所有路径: 1→2=3, 1→3=4，都不等于5");
        assert !result : "不应该找到路径和为5";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 空树
     */
    private static void testCase3(S89_Easy_112_路径总和 solution) {
        TreeNode root = null;
        int targetSum = 0;
        System.out.println("树结构: []");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: false)");
        assert !result : "空树不应该有路径";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 单节点树，目标和匹配
     */
    private static void testCase4(S89_Easy_112_路径总和 solution) {
        TreeNode root = new TreeNode(1);
        int targetSum = 1;
        System.out.println("树结构: [1]");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: true)");
        assert result : "单节点值等于目标和";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 单节点树，目标和不匹配
     */
    private static void testCase5(S89_Easy_112_路径总和 solution) {
        TreeNode root = new TreeNode(1);
        int targetSum = 2;
        System.out.println("树结构: [1]");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: false)");
        assert !result : "单节点值不等于目标和";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 负数节点值
     * .树结构：
     * .    -3
     * .    / \
     * .   9  -10
     * .路径: -3 → -10 = -13 或 -3 → 9 = 6
     */
    private static void testCase6(S89_Easy_112_路径总和 solution) {
        TreeNode root = new TreeNode(-3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(-10);

        int targetSum = -13;
        System.out.println("树结构: [-3,9,-10]");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: true)");
        System.out.println("路径: -3 → -10 = -13");
        assert result : "应该找到路径和为-13";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 目标和为正数，包含负数节点
     * .树结构：
     * .    1
     * .   / \
     * . -2   3
     * .路径: 1 → -2 = -1 或 1 → 3 = 4
     */
    private static void testCase7(S89_Easy_112_路径总和 solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(-2);
        root.right = new TreeNode(3);

        int targetSum = 4;
        System.out.println("树结构: [1,-2,3]");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: true)");
        System.out.println("路径: 1 → 3 = 4");
        assert result : "应该找到路径和为4";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 链式树（左偏）
     * .树结构：
     * .   1
     * .  /
     * . 2
     * ./
     * .3
     * ./
     * .4
     * ./
     * .5
     * .路径: 1 → 2 → 3 → 4 → 5 = 15
     */
    private static void testCase8(S89_Easy_112_路径总和 solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(4);
        root.left.left.left.left = new TreeNode(5);

        int targetSum = 15;
        System.out.println("树结构: [1,2,null,3,null,4,null,5]");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: true)");
        System.out.println("路径: 1 → 2 → 3 → 4 → 5 = 15");
        assert result : "应该找到路径和为15";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 多条路径，只有一条满足
     * .树结构：
     * .      10
     * .     /  \
     * .    5    15
     * .   / \     \
     * .  3   7    18
     * .路径1: 10 → 5 → 3 = 18 ✓
     * .路径2: 10 → 5 → 7 = 22
     * .路径3: 10 → 15 → 18 = 43
     */
    private static void testCase9(S89_Easy_112_路径总和 solution) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.right = new TreeNode(18);

        int targetSum = 18;
        System.out.println("树结构: [10,5,15,3,7,null,18]");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: true)");
        System.out.println("路径: 10 → 5 → 3 = 18");
        assert result : "应该找到路径和为18";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 所有路径都不满足
     * .树结构：
     * .     1
     * .    / \
     * .   2   3
     * .  / \
     * . 4   5
     * .路径: 1→2→4=7, 1→2→5=8, 1→3=4
     */
    private static void testCase10(S89_Easy_112_路径总和 solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        int targetSum = 100;
        System.out.println("树结构: [1,2,3,4,5]");
        System.out.println("目标和: " + targetSum);
        boolean result = solution.hasPathSum(root, targetSum);
        System.out.println("hasPathSum() -> " + result + " (期望: false)");
        System.out.println("所有路径: 1→2→4=7, 1→2→5=8, 1→3=4，都不等于100");
        assert !result : "不应该找到路径和为100";
        System.out.println("✓ 测试10通过");
    }
}

